package DP.打家劫舍;


/**
 * new
 *      打家劫舍 无 []型 dp
 *
 * 总结：
 *  1 拿/不拿
 *      a 先主导i+1+2回溯 后优化map
 *      b 也到 N 叶子
 *     -> 文档已记录
 *
 *  2 * 回溯草图大改
 *       sI 上方 无 /| 分叉 （只有 f后 才 分叉）
 *     i i i
 *
 *  3 map 备忘录
 *      -> 文档 //
 *
 */
public class 打家劫舍198_voidMap_无数组dp {
    // i+1 i+2 自己主导！
    int[] p;
    int n;
    int[] map;
    public int rob(int[] nums) {
        p = nums;
        n = nums.length;

        map = new int[n];
        for (int i = 0; i < n; i++) {
            map[i] = -1;
        }

        return backTrack(0);
    }

    private int backTrack(int ind) {
        if(ind >= n){
            return 0;
        }
        int tou = backTrack(ind+2) + p[ind];
        int butou = backTrack(ind+1);
        return Math.max(tou, butou);
    }

    private int backTrack_m(int ind) {
        if(ind >= n){
            return 0;
        }

        if(map[ind] != -1){
            return map[ind];
        }

        int tou = backTrack_m(ind+2) + p[ind];
        int butou = backTrack_m(ind+1);
        int curMax = Math.max(tou, butou);

        map[ind] = curMax; // 存！
        return curMax;
    }
}
